{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Apply Operations to Make All Array Elements Equal to Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组中的所有元素都等于零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个正整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>你可以对数组执行下述操作 <strong>任意次</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从数组中选出长度为 <code>k</code> 的 <strong>任一</strong> 子数组，并将子数组中每个元素都 <strong>减去</strong> <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你可以使数组中的所有元素都等于 <code>0</code> ，返回&nbsp; <code>true</code><em> </em>；否则，返回<em> </em><code>false</code><em> </em>。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中的一个非空连续元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,2,3,1,1,0], k = 3\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以执行下述操作：\n",
    "- 选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [<em><strong>1</strong></em>,<em><strong>1</strong></em>,<em><strong>2</strong></em>,1,1,0] 。\n",
    "- 选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,<em><strong>1</strong></em>,<em><strong>0</strong></em>,<em><strong>0</strong></em>,0] 。\n",
    "- 选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [<em><strong>0</strong></em>,<em><strong>0</strong></em>,<em><strong>0</strong></em>,0,0,0] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,1,1], k = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法使数组中的所有元素等于 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [apply-operations-to-make-all-array-elements-equal-to-zero](https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [apply-operations-to-make-all-array-elements-equal-to-zero](https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,1,1,0]\\n3', '[1,3,1,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        \n",
    "        diff = 0\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if diff > num:\n",
    "                return False\n",
    "            nums[i], diff = num - diff, num\n",
    "            if i >= k - 1:\n",
    "                diff -= nums[i - k + 1]\n",
    "        \n",
    "        return diff == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        for i in range(n-1,0,-1):\n",
    "            nums[i]-=nums[i-1]\n",
    "        # print(nums)\n",
    "        for i in range(n-k):\n",
    "            if nums[i]<0:\n",
    "                return False\n",
    "            nums[i+k]+=nums[i]\n",
    "            nums[i]=0\n",
    "            # print(nums)\n",
    "        nums[n-k]=0\n",
    "        # print(nums)\n",
    "        return not any(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        d = [0] * (n + 1) \n",
    "        tot = 0 \n",
    "        for i in range(n):\n",
    "            tot += d[i] \n",
    "            nums[i] += tot \n",
    "            if i + k - 1 < n and nums[i] > 0:\n",
    "                d[i] -= nums[i] \n",
    "                d[min(i+k, n)] += nums[i] \n",
    "                tot -= nums[i]\n",
    "                nums[i] = 0 \n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i] != 0:\n",
    "                return False \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        if k == 1:\n",
    "            return True\n",
    "        n = len(nums)\n",
    "        i = 1\n",
    "        temp = nums[0]\n",
    "        res = 0\n",
    "        t = 1\n",
    "        while i < n:\n",
    "            if i - k < 0:\n",
    "                nums[i] -= temp + res\n",
    "                res += nums[i]\n",
    "            elif i - k >= 0 and nums[i - k + 1] >= 0:\n",
    "                nums[i],res = nums[i] - res,nums[i] - nums[i - k + 1]\n",
    "            else:\n",
    "                return False\n",
    "            i += 1\n",
    "        return nums[-k + 1:].count(0) == k - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        s=sum(nums)\n",
    "        # print(s)\n",
    "        for i in range(n-1,0,-1):\n",
    "            nums[i]-=nums[i-1]\n",
    "        # print(nums)\n",
    "        for i in range(n-k):\n",
    "            if nums[i]<0:\n",
    "                return False\n",
    "            nums[i+k]+=nums[i]\n",
    "            nums[i]=0\n",
    "            # print(nums)\n",
    "        nums[n-k]=0\n",
    "        # print(nums)\n",
    "        return not any(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        d = [0] * (len(nums)+1)\n",
    "        sum_d = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum_d -= d[i]\n",
    "            nums[i] -= sum_d\n",
    "            if nums[i] == 0:\n",
    "                continue\n",
    "            if nums[i] < 0 or i+k > len(nums):\n",
    "                return False\n",
    "            d[i+k] += nums[i]\n",
    "            sum_d += nums[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "    #     if k == 1:\n",
    "    #         return True\n",
    "        \n",
    "    #     nums.append(0)\n",
    "\n",
    "    #     ps = [nums[0]] + [0] * (len(nums) - 1)\n",
    "    #     for i in range(1, len(nums)):\n",
    "    #         ps[i] = nums[i] - nums[i-1]\n",
    "        \n",
    "\n",
    "    #     # print(ps)\n",
    "\n",
    "    #     for i, n in enumerate(ps):\n",
    "\n",
    "    #         if n == 0:\n",
    "    #             continue\n",
    "\n",
    "    #         if n < 0:\n",
    "    #             return False\n",
    "            \n",
    "    #         # the key point is if i+k == len(nums), it's valid and should update the diff arr\n",
    "    #         # add 0 to original nums to make the update valid\n",
    "    #         if i + k < len(nums):\n",
    "    #             ps[i+k] += n\n",
    "    #         else:\n",
    "    #             return False\n",
    "\n",
    "\n",
    "    #     # for i, n in enumerate(nums):\n",
    "    #     #     if n > 0:\n",
    "    #     #         for j in range(k):\n",
    "    #     #             if i + j >= len(nums) or nums[i+j] < n:\n",
    "    #     #                 return False\n",
    "                    \n",
    "    #     #             nums[i + j] -= n\n",
    "        \n",
    "    #     return True\n",
    "                        \n",
    "\n",
    "    # from answer do not calcilate the diff but use it when iterate the nums\n",
    "    # 156ms -> 112ms\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        d = [0] * (n + 1)\n",
    "\n",
    "        sum_d = 0\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            sum_d += d[i]\n",
    "\n",
    "            x += sum_d\n",
    "\n",
    "            if x == 0: continue  # 无需操作\n",
    "\n",
    "            if x < 0 or i + k > n: return False  # 无法操作\n",
    "\n",
    "            sum_d -= x  # 直接加到 sum_d 中\n",
    "\n",
    "            d[i + k] += x\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        d = [0] * (n + 1)\n",
    "        sum_d = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            sum_d += d[i]\n",
    "            x += sum_d\n",
    "            if x == 0: continue  # 无需操作\n",
    "            if x < 0 or i + k > n: return False  # 无法操作\n",
    "            sum_d -= x  # 直接加到 sum_d 中\n",
    "            d[i + k] += x\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        d = [0] * (n + 1)\n",
    "        sum_d = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            sum_d += d[i]\n",
    "            x += sum_d\n",
    "            if x == 0: continue  # 无需操作\n",
    "            if x < 0 or i + k > n: return False  # 无法操作\n",
    "            sum_d -= x  # 直接加到 sum_d 中\n",
    "            d[i + k] += x\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkArray(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        d = [0] * (n + 1)\n",
    "        d[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            d[i] = nums[i] - nums[i - 1]\n",
    "        # print(d)\n",
    "        for i in range(n - k + 1):\n",
    "            if d[i] > 0:\n",
    "                d[i + k] += d[i]\n",
    "                d[i] = 0\n",
    "            elif d[i] < 0:\n",
    "                return False\n",
    "        for i in range(n - k + 1, n):\n",
    "            if d[i] != 0: return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
